На плоскости задано множество точек с целочисленными координатами. Необходимо найти минимально возможную площадь невырожденного (т. е. имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа – координаты очередной точки.
Пример входных данных:
3
6 6
-8 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна
напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных:
48
Решение задачи
Как известно биссектриса - это крыса, которая делит угол пополам. Отсюда, можно догадаться, что точка лежащая на биссектрисе имеет одинаковую абсолютную (без знака) координату по x и y. Например: (6,6), (8,-8), (-10,-10). То есть при решении задачи для запоминании координаты точки достаточно запомнить одно число: абсолютное значение X или Y. Далее задача сводится к нахождение двух координат с минимальными абсолютными значениями, то есть в нашем случае к нахождению двух минимальных чисел. В конце нужно посчитать площадь.
Нарисуйте на бумаге треугольник с координатами (0,0),(6,6),(-4,4), вспомните теорему Пифагора и легко поймете формулу вычисления площади..
Так же нужно проверить, что такой треугольник может существовать. В нашей задаче для этого достаточно, чтобы точки не лежали на одной прямой. Для проверки этого можно перемножить знаки координат. Например, у точек (6,6) и (-4,4) произведение знаков будет -1, такой треугольник может существовать. А у точек (-4,4) и (5,-5), произведение равно +1, это вырожденный треугольник.
var
N: integer; {количество точек}
x, y: integer; {координаты очередной точки}
tmin1, tmin2: integer; {минимальные координаты точек}
z: Integer;{Проверка на вырожденость}
s: real; {площадь}
i: integer;
begin
readln(N);
tmin1 := MaxInt;tmin2 := MaxInt;
z:=1;
for i := 1 to N do
begin
readln(x, y);
if (abs(x) = abs(y)) then begin
if abs(x) < tmin1 then begin
tmin2 := tmin1;
tmin1 := abs(x);
z:=z*Sign(x)*Sign(y);
end
else
if abs(x) < tmin2 then begin
tmin2 := abs(x);
z:=z*Sign(x)*Sign(y);
end;
end;
end;
if z=1 then writeln('Треугольник не существует')
else begin
s := tmin1 * tmin2 / 2;
writeln(s);
end;
end.